package com.leetcodehot.problems;

import java.util.Arrays;

public class problems712 {

    public int minimumDeleteSum(String s1, String s2) {
        char[] char1 = s1.toCharArray();
        char[] char2 = s2.toCharArray();
        int len1 = char1.length;
        int len2 = char2.length;
        int[][] memo = new int[len1 + 1][len2 + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dfs(len1 - 1, len2 - 1, char1, char2, memo);
    }

    private int dfs(int i, int j, char[] char1, char[] char2, int[][] memo) {
        if (i < 0) {
            int sum = 0;
            for (int k = 0; k <= j; k++) {
                sum += char2[k];
            }
            return sum;
        }
        if (j < 0) {
            int sum = 0;
            for (int k = 0; k <= i; k++) {
                sum += char1[k];
            }
            return sum;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        //相同
        if (char1[i] == char2[j]) {
            return memo[i][j] = dfs(i - 1, j - 1, char1, char2, memo);
        }
        //不同
        int ans = Integer.MAX_VALUE;
        //删除
        ans = Math.min(ans, dfs(i - 1, j, char1, char2, memo) + char1[i]);
        //新增
        ans = Math.min(ans, dfs(i, j - 1, char1, char2, memo) + char2[j]);
        //替换(这里比较特殊 替换看成两步)
        ans = Math.min(ans, dfs(i - 1, j - 1, char1, char2, memo) + char1[i] + char2[j]);
        return memo[i][j] = ans;
    }
}
